package com.yulan.dp.package_01;

import java.util.Scanner;

/**
 * [编程题]找零

 *
 * Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。
 * 现在小Y使用1024元的纸币购买了一件价值为N (0 < N \le 1024)N(0<N≤1024)的商品，请问最少他会收到多少硬币？
 */
public class findZero {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int n = 1024 - scanner.nextInt();
            int[] dp = new int[n+1];
            for(int i = 0;i<dp.length;i++){
                dp[i] = i;
            }

            int[] moneys = {1,4,16,64};

            for(int i = 1; i<= n;i++){
                for(int j = 0;j<moneys.length;j++){
                    if( i - moneys[j] >= 0)
                        dp[i] = Math.min(dp[i],dp[i-moneys[j]] + 1);
                }
            }

            System.out.println(dp[n]);
        }
    }
}



































